package com.jia.explore.dynamicprogramming.knapsack;

import java.util.Scanner;

/**
 * @program: Leetcode
 * @description: 完全背包问题   0-1背包倒过来
 *      https://www.acwing.com/problem/content/3/
 *
 * @author: STU756
 * @create: 2020-08-11 12:47
 */
public class Dy_CompleteBackpack {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int count = 1;
        int N = 1010;
        int[] v = new int[N];
        int[] w = new int[N];
        while(count <= n) {
            v[count] = scanner.nextInt();
            w[count] = scanner.nextInt();
            ++count;
        }
        int[] dp = new int[N];
        for(int i = 1; i <= n; i++) {
            //正循环，会把dp[j]上一场前面的值覆盖掉为当前层的值
            for(int j = v[i]; j <= m; j++) {
                // f[k] = Math.max(f[k], f[k-v[j]] + w[j]);
                dp[j] = Math.max(dp[j],dp[j-v[i]] + w[i]);
            }
        }
        System.out.println(dp[m]);
    }
}
